package com.example.leetcode.array;

import java.util.Arrays;

class SolutionLCP72 {
    public int[] supplyWagon(int[] supplies) {
        int n = supplies.length;
        int[] merge = supplies;
        while (merge.length > n / 2) {
            merge = mergeOne(merge);
        }
        return merge;
    }

    private static int[] mergeOne(int[] supplies) {
        int n = supplies.length;
        int minIndex = 1;
        int minSum = supplies[1] + supplies[0];
        for (int i = 1; i < n; i++) {
            int sum = supplies[i] + supplies[i - 1];
            if (sum < minSum) {
                minSum = sum;
                minIndex = i;
            }
        }
        supplies[minIndex] = minSum;
        supplies[minIndex - 1] = 0;
        int[] result = new int[n - 1];
        System.arraycopy(supplies, 0, result, 0, minIndex - 1);
        System.arraycopy(supplies, minIndex, result, minIndex - 1, n - minIndex);
        return result;
    }
}

public class LCP72 {
    public static void main(String[] args) {
        SolutionLCP72 solutionLCP72 = new SolutionLCP72();
        int[] supplies = {7, 3, 6, 1, 8};
        int[] supplies1 = {1, 3, 1, 5};
        System.out.println(Arrays.toString(solutionLCP72.supplyWagon(supplies)));
        System.out.println(Arrays.toString(solutionLCP72.supplyWagon(supplies1)));
    }
}
